다음과 같이 $x_1, x_2, \cdots, x_n$ 이라는 $n$ 개의 미지수를 가지는 방정식을 연립 방정식(system of equations)이라고 한다.
$$ \begin{matrix} a_{11} x_1 & + \;& a_{12} x_2 &\; + \cdots + \;& a_{1M} x_M &\; = \;& b_1 \\ a_{21} x_1 & + \;& a_{22} x_2 &\; + \cdots + \;& a_{2M} x_M &\; = \;& b_2 \\ \vdots\;\;\; & & \vdots\;\;\; & & \vdots\;\;\; & & \;\vdots \\ a_{N1} x_1 & + \;& a_{N2} x_2 &\; + \cdots + \;& a_{NM} x_M &\; = \;& b_N \\ \end{matrix} $$행렬의 곱셈을 이용하면 이 연립 방정식은 다음과 같이 간단하게 쓸 수 있다. $$ Ax = b $$
이 식에서 $A, x, b$ 는 다음과 같이 정의한다.
$$ A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} $$$$ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} $$$$ b= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$$$ Ax = b \;\;\;\;\; \rightarrow \;\;\;\;\; \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1M} \\ a_{21} & a_{22} & \cdots & a_{2M} \\ \vdots & \vdots & \ddots & \vdots \\ a_{N1} & a_{N2} & \cdots & a_{NM} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_M \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_N \end{bmatrix} $$만약 $A, x, b$가 행렬이 아닌 실수라면 이 식은 나눗셈을 사용하여 다음과 같이 쉽게 풀 수 있을 것이다.
$$ x = \dfrac{b}{A} $$그러나 행렬은 나눗셈이 정의되지 않으므로 이 식은 사용할 수 없다. 대신 역행렬(inverse)을 사용하여 이 식을 쉽게 풀 수 있다.
정방 행렬(square matrix) $A\;(A \in \mathbb{R}^{M \times M}) $ 에 대한 역행렬은 $A^{-1}$ 이란 기호로 표시한다.
역행렬 $A^{-1}$은 원래의 행렬 $A$와 다음 관계를 만족하는 정방 행렬을 말한다. $I$는 단위 행렬(identity matrix)이다.
$$ A^{-1} A = A A^{-1} = I $$두 개 이상의 정방 행렬의 곱은 마찬가지로 같은 크기의 정방행렬이 되는데 이러한 행렬의 곱의 역행렬에 대해서는 다음 성질이 성립한다.
$$ (AB)^{-1} = B^{-1} A^{-1} $$$$ (ABC)^{-1} = C^{-1} B^{-1} A^{-1} $$미지수의 수와 방정식의 수가 같다면 행렬 $A$ 는 정방 행렬이 된다.
만약 행렬 $A$의 역행렬 $ A^{-1} $ 이 존재한다면 역행렬의 정의에서 연립 방정식의 해는 다음과 같이 구해진다.
$$ Ax = b $$$$ A^{-1}Ax = A^{-1}b $$$$ Ix = A^{-1}b $$$$ x = A^{-1}b $$NumPy의 linalg 서브패키지에는 역행렬을 구하는 inv 라는 명령어가 존재한다. 그러나 실제 계산시에는 수치해석 상의 여러가지 문제로 inv 명령어 보다는 lstsq (least square) 명령어를 사용한다.
In [1]:
A = np.array([[1, 3, -2], [3, 5, 6], [2, 4, 3]])
A
Out[1]:
In [2]:
b = np.array([[5], [7], [8]])
b
Out[2]:
In [4]:
Ainv = np.linalg.inv(A)
Ainv
Out[4]:
In [5]:
x = np.dot(Ainv, b)
x
Out[5]:
In [6]:
np.dot(A, x) - b
Out[6]:
In [12]:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out[12]:
위 해결 방법에는 두 가지 의문이 존재한다. 우선 역행렬이 존재하는지 어떻게 알 수 있는가? 또 두 번째 만약 미지수의 수와 방정식의 수가 다르다면 어떻게 되는가?
우선 역행렬이 존재하는지 알아보는 방법의 하나로 행렬식(determinant)라는 정방 행렬의 특징을 계산하는 방법이다. 행렬 $A$ 에 대한 행렬식은 $\text{det}A$라는 기호로 표기한다.
행렬식(determinant)의 수학적인 정의는 상당히 복잡하므로 여기에서는 생략한다. 다만 몇가지 크기의 정방 행렬에 대해서는 다음과 같은 수식으로 구할 수 있다.
2×2 행렬의 행렬식 $$\det\begin{bmatrix}a&b\\c&d\end{bmatrix}=ad-bc$$
3×3 행렬의 행렬식 $$\det\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}=aei+bfg+cdh-ceg-bdi-afh$$
NumPy에서는 det 명령으로 행렬식의 값을 구할 수 있다.
In [13]:
np.random.seed(0)
A = np.random.randn(3, 3)
A
Out[13]:
In [14]:
np.linalg.det(A)
Out[14]:
행렬식과 역행렬 사이에는 다음의 관계가 있다.
행렬식의 값이 0이 아니면 역행렬이 존재한다. 반대로 역행렬이 존재하면 행렬식의 값은 0이 아니다.
연립 방정식은 다음과 같은 세 종류가 있다.
1번의 경우는 앞에서 다루었다. 2번의 경우에는 너무 많은 해가 존재할 수 있다. 3번의 경우에는 2번과 반대로 모든 조건을 만족하는 해가 하나도 존재할 수 없을 수도 있다.
그런데 데이터 분석 문제에서는 $A$ 를 feature matrix, $x$ 를 가중치 벡터 $w$ 라고 보았을 때 데이터의 수가 가중치의 갯수보다 많은 경우가 일반적이다. 다만 이 때는 방정식이 정확하게 등호를 이루기를 바라지는 않는다. 즉, 대략적으로만 좌변과 우변이 비슷하면 되는 경우이다.
$$ Ax \approx b $$이 경우에는 좌변과 우변의 차이를 최소하하는 문제로 바꾸어 풀 수 있다.
$$ e = Ax-b $$$$ e^Te = (Ax-b)^T(Ax-b) $$$$ x = \text{arg} \min_x e^Te = \text{arg} \min_x \; (Ax-b)^T(Ax-b) $$이러한 문제를 최소 자승(Least Square) 문제라고 한다.
최소 자승 문제의 답은 $A^TA$ 는 항상 정방행렬이 된다는 점을 사용하여 다음과 같이 풀 수 있다.
$$ Ax = b $$$$ A^TAx = A^Tb $$$$ (A^TA)x = A^Tb $$$$ x = (A^TA)^{-1}A^T b $$$$ x = ((A^TA)^{-1}A^T) b $$이 값이 최소 자승 문제의 답이 된다는 것은 행렬의 미분을 사용하여 증명할 수 있다. 여기에서 행렬 $(A^TA)^{-1}A^T$ 를 행렬 $A$ 의 의사 역행렬(pseudo inverse)라고 하며 다음과 같이 $ A^{+}$ 로 표기하기도 한다.
$$ A^{+} = (A^TA)^{-1}A^T $$NumPy의 lstsq 명령은 사실 이러한 최소 자승 문제를 푸는 명령이다.
In [15]:
A = np.array([[2, 0], [-1, 1], [0, 2]])
A
Out[15]:
In [16]:
b = np.array([[1], [0], [-1]])
b
Out[16]:
In [17]:
Apinv = np.dot(np.linalg.inv(np.dot(A.T, A)), A.T)
Apinv
Out[17]:
In [18]:
x = np.dot(Apinv, b)
x
Out[18]:
In [19]:
np.dot(A, x) - b
Out[19]:
In [20]:
x, resid, rank, s = np.linalg.lstsq(A, b)
x
Out[20]: